{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1600245029040",
   "display_name": "Python 3.8.5 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "用line[i][x-1]的数组来记录i行上是否有重复的数字x\n",
    "\n",
    "用column[j][x-1]的数组来记录i列上是否有重复的数字x\n",
    "\n",
    "用block[i/3][j/3][x-1] 的数组来记录在9宫格是否有重复的数字x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        SPACE = '.'\n",
    "        def dfs(pos):\n",
    "            nonlocal valid\n",
    "            # 如果找完全部的空格\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "\n",
    "            i, j = spaces[pos]\n",
    "            # print(i,j)\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i//3][j//3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = True\n",
    "                    board[i][j] = str(digit+1)     \n",
    "                    dfs(pos+1)\n",
    "                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = False\n",
    "                if valid:\n",
    "                    return \n",
    "            \n",
    "\n",
    "\n",
    "        valid = False\n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] *9 for _a  in range(3)] for _b in range(3)]\n",
    "        spaces = []\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == SPACE:\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "\n",
    "                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = True\n",
    "        # print(column)\n",
    "        dfs(0)\n",
    "        # print(valid)\n",
    "        # print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "board1 = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "\n",
    "x = Solution().solveSudoku(board1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['5', '3', '4', '6', '7', '8', '9', '2', '2'],\n ['6', '7', '2', '1', '9', '5', '8', '4', '4'],\n ['1', '9', '8', '3', '4', '2', '7', '6', '7'],\n ['8', '5', '9', '7', '6', '4', '4', '2', '3'],\n ['4', '2', '6', '8', '5', '3', '7', '9', '1'],\n ['7', '1', '3', '9', '2', '4', '8', '5', '6'],\n ['9', '6', '7', '5', '3', '7', '2', '8', '4'],\n ['3', '8', '7', '4', '1', '9', '6', '3', '5'],\n ['3', '4', '5', '2', '8', '6', '1', '7', '9']]"
     },
     "metadata": {},
     "execution_count": 92
    }
   ],
   "source": [
    "board1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def s(x):\n",
    "    x[0] = 3\n",
    "\n",
    "bb= [1,2,3]\n",
    "s(bb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[3, 2, 3]"
     },
     "metadata": {},
     "execution_count": 52
    }
   ],
   "source": [
    "bb"
   ]
  },
  {
   "source": [
    "1.用错了赋值用成了等于号，也是醉了\n",
    "\n",
    "2. `if valid: return`放在了for外面，也导致了错了，还看了半天。。。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "        print(block)\n",
    "        dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "[[[False, False, True, False, True, True, False, True, True], [True, False, False, False, True, False, True, False, True], [False, False, False, False, False, True, False, False, False]], [[False, False, False, True, False, False, True, True, False], [False, True, True, False, False, True, False, True, False], [True, False, True, False, False, True, False, False, False]], [[False, False, False, False, False, True, False, False, False], [True, False, False, True, False, False, False, True, True], [False, True, False, False, True, False, True, True, True]]]\n"
    }
   ],
   "source": [
    "board1 = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "\n",
    "x = Solution().solveSudoku(board1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['5', '3', '4', '6', '7', '8', '9', '1', '2'],\n ['6', '7', '2', '1', '9', '5', '3', '4', '8'],\n ['1', '9', '8', '3', '4', '2', '5', '6', '7'],\n ['8', '5', '9', '7', '6', '1', '4', '2', '3'],\n ['4', '2', '6', '8', '5', '3', '7', '9', '1'],\n ['7', '1', '3', '9', '2', '4', '8', '5', '6'],\n ['9', '6', '1', '5', '3', '7', '2', '8', '4'],\n ['2', '8', '7', '4', '1', '9', '6', '3', '5'],\n ['3', '4', '5', '2', '8', '6', '1', '7', '9']]"
     },
     "metadata": {},
     "execution_count": 83
    }
   ],
   "source": [
    "board1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i//3][j//3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = True\n",
    "                    board[i][j] = str(digit+1)     \n",
    "                    dfs(pos+1)\n",
    "                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = False\n",
    "            if valid:\n",
    "                return \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return"
   ]
  }
 ]
}